#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
int T,f[N][N*N],n,m,mod;
int qpow(int x,int y)
{
	int res = 1;
	while(y)
	{
		if(y&1) res = res*x%mod;
		y>>=1;
		x = x*x%mod;
	}
	return res;
}
int inv(int x)
{
	return qpow(x,mod-2);
}
signed main()
{
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>mod>>T;
	while(T--)
	{
		cin>>n>>m;
		memset(f,0,sizeof f);
		for(int i = 0;i<=n;i++)
			f[i][0] = 1;
		for(int i = 1;i<=n;i++)
		{
			int sum = f[i-1][0],lt = 0;
			for(int j = 1;j<=n*m;j++)
			{
				sum+=f[i-1][j];
				if(j-lt>m) sum-=f[i-1][lt++];
				sum = (sum%mod+mod)%mod;
				f[i][j] = sum;
			}
		}
		int ans = 0,sum = 0;
		for(int i = 1;i<=m*n;i++)
			(sum+=f[n][i-1])%=mod,(ans+=f[n][i]*sum%mod)%=mod;
		cout<<ans*inv(qpow(m+1,2*n))%mod<<'\n';
	}
	return 0;
}

